#pragma once

#include <string>
#include <vector>

namespace solution_051
{

class Solution
{
public:
    std::vector< std::vector<std::string> > solveNQueens(int n)
    {
        m_off = n - 1;
        m_mask_col.resize(n, 0);
        m_mask_anti.resize(2 * n - 1, 0);
        m_mask_diag.resize(2 * n - 1, 0);

        std::vector<int> path;

        for (int c = 0; c < n / 2; ++c) {
            path.push_back(c);
            m_mask_col.at(c) = 1;
            m_mask_anti.at(c) = 1;
            m_mask_diag.at(m_off + c) = 1;
            backtrack(path, n);
            m_mask_col.at(c) = 0;
            m_mask_anti.at(c) = 0;
            m_mask_diag.at(m_off + c) = 0;
            path.pop_back();
        }

        int m = m_slns.size();
        for (int i = 0; i < m; ++i) {
            auto& mirror = m_slns.emplace_back();
            auto& origin = m_slns.at(i);
            for (const std::string& row : origin)
                mirror.emplace_back(row.crbegin(), row.crend());
        }

        if (n % 2) {
            int c = n / 2;
            path.push_back(c);
            m_mask_col.at(c) = 1;
            m_mask_anti.at(c) = 1;
            m_mask_diag.at(m_off + c) = 1;
            backtrack(path, n);
            m_mask_col.at(c) = 0;
            m_mask_anti.at(c) = 0;
            m_mask_diag.at(m_off + c) = 0;
            path.pop_back();
        }

        return m_slns;
    }

private:
    void backtrack(std::vector<int>& path, int n)
    {
        if ((int)path.size() == n) {
            auto& sln = m_slns.emplace_back(n, std::string(n, '.'));
            for (int i = 0; i < n; ++i)
                sln.at(i).at(path.at(i)) = 'Q';
            return;
        }
        int r = path.size();
        for (int c = 0; c < n; ++c) {
            if (m_mask_col.at(c) || m_mask_anti.at(c + r) || m_mask_diag.at(m_off + c - r))
                continue;
            path.push_back(c);
            m_mask_col.at(c) = 1;
            m_mask_anti.at(c + r) = 1;
            m_mask_diag.at(m_off + c - r) = 1;
            backtrack(path, n);
            m_mask_col.at(c) = 0;
            m_mask_anti.at(c + r) = 0;
            m_mask_diag.at(m_off + c - r) = 0;
            path.pop_back();
        }
    }

    int m_off;
    std::vector<unsigned char> m_mask_col;
    std::vector<unsigned char> m_mask_diag;
    std::vector<unsigned char> m_mask_anti;
    std::vector< std::vector<std::string> > m_slns;
};

}  /* namespace solution_051 */
